package binarySearch;

public class D230716 {
    // 二分查找-I
    public int search (int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    // 二维数组中的查找
    public boolean Find(int target, int [][] array) {
        int i = 0;
        int j = array[0].length - 1;
        // 从右上角开始遍历
        // 右上角这个值, 在这一行里时最大的, 在这一列里是最小的
        while (i < array.length && j >= 0) {
            if (array[i][j] < target) {
                // 小于目标值, 排除这一行
                i++;
            } else if (array[i][j] > target) {
                // 大于目标值, 排除这一列
                j--;
            } else {
                return true;
            }
        }
        return false;
    }

    // 寻找峰值
    public int findPeakElement (int[] nums) {
        // 边界看为最小值，且只需要找到一个波峰即可
        int n = nums.length;
        if (n == 1 || nums[0] > nums[1]) {
            // 只有一个元素，或第一个元素大于第二个元素
            return 0;
        }
        if (nums[n - 1] > nums[n - 2]) {
            // 倒一元素 大于 倒二元素
            return n - 1;
        }
        int left = 0, right = n - 1, mid;
        while (left < right) {
            mid = (left + right) / 2;
            if (nums[mid] > nums[mid + 1]) {
                // 右边是下坡，不一定有波峰
                right = mid;
            } else {
                // 右边是上坡，一定有波峰
                left = mid + 1;
            }
        }
        return left;
    }
}
